package ll1;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;

import scanner.MiniReScan;

public class LL1Gen {
	private ArrayList<String> tokens;
	private ArrayList<String> nonTerm; //index 0 is start, global nonterminals speed up first set and a count of unique nonterminals
	private ArrayList<LL1Node> grammar;
	private ArrayList<Fset> first;
	private ArrayList<Fset> follow;
	private LL1Table parseTable;
	private ArrayList<String> cumlativeSet;	//cumlative of first or follow set
	private String startToken;
	private String errLog;
	private boolean errFound;
	
	/**
	 * Reads in the rules/grammar for this script language and creates a LL1 parse table for that language
	 * @param tokenList	- keywords/symbols in this language
	 * @param path - the location of file containing this rule/grammar
	 * @throws IOException
	 */
	public LL1Gen(ArrayList<String> tokenList, ArrayList<LL1Node> rules, String starting){
		errFound = false;
		setErrLog("");
		startToken = starting;
		tokens = tokenList;
		if(!tokens.contains("ID")){
			tokens.add("ID");
		}
		if(!tokens.contains("epsilon")){
			tokens.add("epsilon");
		}
		if(!tokens.contains("REGEX")){
			tokens.add("REGEX");
		}
		if(!tokens.contains("ASCII-STR")){
			tokens.add("ASCII-STR");
		}
		first = new ArrayList<Fset>();
		follow = new ArrayList<Fset>();
		nonTerm = new ArrayList<String>();
		
		int index = 0;
		LL1Node temp;
		while(index < rules.size()){	//scan the grammar
			temp = rules.get(index);
			//Destroy "|" sections if they exist
			if(temp.getOrSymbols() > 0){	//need to split up rule
				ArrayList<Token> stuff = temp.getContent();
				ArrayList<Token> newContent = new ArrayList<Token>();
				rules.remove(index);
				LL1Node addNew = new LL1Node(temp.getName());
				for(int i = 0; i < stuff.size(); i++){
					if(stuff.get(i).getName().equals("|") || i == (stuff.size() - 1)){
						if(i == (stuff.size() - 1)){
							newContent.add(stuff.get(i));
						}
						addNew.setContent(newContent);
						rules.add(addNew);
						newContent = new ArrayList<Token>();
						addNew = new LL1Node(temp.getName());
					}
					else{
						newContent.add(stuff.get(i));
					}
				}
				index--;
			}
			index++;
		}
		/**index = 0;
		while(index < rules.size() && rules.get(index) != null){
			index++;
		}**/
		grammar = new ArrayList<LL1Node>(index);
		for(LL1Node node : rules){		//populate the nonterminal data-structure
			if(node == null){
				
			}
			else{
				grammar.add(node);
				if(!nonTerm.contains(node.getName())){
					nonTerm.add(node.getName());
				}
			}
		}
		
		for(String nt : nonTerm){
			//Get the first set
			getFirstSet(nt);
		}
		
		//After the first set is done get the follow set
		getFollowSet();
		
		if(errFound){
			return;
		}
		
		//Keep doing follow until it stablizes
		repeatFollow();
		
		if(errFound){
			return;
		}
		
		//Create a parse table with this information
		createTable();
		
	}
	
	private void getFirstSet(String rule){
		cumlativeSet = new ArrayList<String>();
		Fset temp = new Fset(true, rule);
		ArrayList<LL1Node> multiRule = findRules(rule);
		for(LL1Node node : multiRule){
			firstSetOf(node);
		}
		temp.setSet(cumlativeSet);
		first.add(temp);
	}
	
	/**
	 * Helper method for getting first set (multiple call version)
	 * @param rule
	 * @return list of terminals
	 */
	private void firstSetOf(LL1Node rule){
		ArrayList<Token> stuff = rule.getContent();
		if(stuff.get(0).isTerminal()){							//The first one is a terminal
			if(!cumlativeSet.contains(stuff.get(0).getName())){
				cumlativeSet.add(stuff.get(0).getName());
			}
		}
		else{													//The first one is non-terminal
			ArrayList<LL1Node> temp = findRules(stuff.get(0).getName());
			for(LL1Node node : temp){
				firstSetOf(node);
			}
		}
		
		for(int i = 1; i < rule.getContent().size(); i++){	//Checks for | (OR)
			if(stuff.get(i).getName().equals("|")){
				if(stuff.get(i + 1).isTerminal()){							//The first one is a terminal
					if(!cumlativeSet.contains(stuff.get(i + 1).getName())){
						cumlativeSet.add(stuff.get(i + 1).getName());
					}
				}
				else{													//The first one is non-terminal
					ArrayList<LL1Node> temp = findRules(stuff.get(i + 1).getName());
					for(LL1Node node : temp){
						firstSetOf(node);
					}
				}
			}
		}
	}
	
	private void getFollowSet(){
		//Initialize follow set
		for(String element : nonTerm){
			follow.add(new Fset(false, element));
		}
		follow.get(findInFollow(startToken)).addInTo("$");	//start symbol gets dollar sign
		Fset temp;
		for(LL1Node rule : grammar){						//go through the grammar
			if(errFound){
				break;
			}
			ArrayList<Token> stuff = rule.getContent();		//start in contents
			for(int i = 0; i < stuff.size(); i++){			//go through each element in the rule
				if(stuff.get(i).getName().equals("|")){		//CATCHES the | (OR) symbol following a terminal
					i++;
				}
				if(!tokens.contains(stuff.get(i).getName())){				//find nonterminals PREVIOUSLY !stuff.get(i).isTerminal()
					if(findInFollow(stuff.get(i).getName()) < 0){
						break;
					}
					temp = follow.get(findInFollow(stuff.get(i).getName()));
					if(i == stuff.size() - 1 || stuff.get(i + 1).getName().equals("|")){				//check if we reached the last non-terminal rule OR the next symbol is a "|" symbol
						ArrayList<String> followSetStuff = follow.get(findInFollow(rule.getName())).getSet();	//this rule elements gets the follow set of the rule it reside in
						for(String element : followSetStuff){
							temp.addInTo(element);
						}
						if(i != stuff.size() - 1 && stuff.get(i + 1).getName().equals("|")){	//skip "|"
							i++;
						}
					}
					else{									//call the first set on next element
						if(stuff.get(i + 1).isTerminal()){	//if the next element is a terminal
							temp.addInTo(stuff.get(i + 1).getName());	//put the terminal itself into it
						}
						else{								//if the next element is a nonterminal
							ArrayList<String> thisFirstSetStuff = first.get(findInFirst(stuff.get(i + 1).getName())).getSet();
							for(String element : thisFirstSetStuff){	//put in the elements of the first set into it
								if(!element.equals("epsilon")){
									temp.addInTo(element);
								}
							}
						}
					}
				}
			}
		}
	}
	
	/**
	 * Waterfall follow
	 */
	private void repeatFollow(){
		boolean changed = true; //tells us if there has been a change in follow sets, if there is a change keep going and waterfall
		while(changed){
			changed = false;									//set to false since we are doing a fresh scan
			for(LL1Node rule : grammar){						//go through the grammar
				ArrayList<Token> stuff = rule.getContent();		//go into contents
				if(!stuff.get(rule.getContent().size() - 1).isTerminal()){		//check if the end is a terminal 
					Fset temp = follow.get(findInFollow(stuff.get(rule.getContent().size() - 1).getName()));		//it is nonterminal 
					ArrayList<String> followSetStuff = follow.get(findInFollow(rule.getName())).getSet();	//this rule elements gets the follow set of the rule it reside in
					for(String element : followSetStuff){
						if(temp.addInTo(element)){
							changed = true;						//fall to this statement if an addition was successful signaling an update
						}
					}
				}
			}
		}
	}
	
	/**
	 * Finds the follow set within the global data structure for follow
	 * @param name
	 * @return the index the rule is contained in
	 */
	private int findInFollow(String name){
		for(int i = 0; i < follow.size(); i++){
			if(follow.get(i).getName().equals(name)){
				return i;
			}
		}
		setErrLog(getErrLog() + ("This is nonexistant in follow set :'" + name + "'\n"));
		errFound = true;
		return -1;
	}
	
	/**
	 * Finds the first set within the global data structure for first
	 * @param name
	 * @return the index the rule is contained in
	 */
	private int findInFirst(String name){
		for(int i = 0; i < first.size(); i++){
			if(first.get(i).getName().equals(name)){
				return i;
			}
		}
		setErrLog(getErrLog() + ("This is nonexistant in first set :'" + name + "'\n"));
		errFound = true;
		return -1;
	}
	
	/**
	 * Finds the rules in the grammar
	 * @param name
	 * @return whole grammar rule
	 */
	private ArrayList<LL1Node> findRules(String name){
		ArrayList<LL1Node> temp = new ArrayList<LL1Node>();
		for(int index = 0; index < grammar.size(); index++){
			if(name.equals(grammar.get(index).getName())){
				temp.add(grammar.get(index));
			}
		}
		return temp;
	}
	
	/**
	 * Creates the LL1 Parse Table	
	 */
	private void createTable(){
		ArrayList<String> firstSet;
		Fset followSet;
		parseTable = new LL1Table(tokens);
		for(LL1Node rule : grammar){
			firstSet = findFirstOf(rule.getContent().get(0).getName());
			for(String element : firstSet){
				if(element.equals("epsilon")){
					LL1Node node = new LL1Node(rule.getName());
					ArrayList<Token> temp = new ArrayList<Token>();
					temp.add(new Token("epilson", true));
					node.setContent(temp);
					followSet = follow.get(findInFirst(rule.getName()));
					for(String s : followSet.getSet()){
						parseTable.addEntry(node, s);
					}
				}
				else{
					parseTable.addEntry(rule, element);
				}
			}
		}
	}
	
	public LL1Table getTable(){
		return parseTable;
	}
	
	private ArrayList<String> findFirstOf(String tokenName){
		ArrayList<String> temp = new ArrayList<String>();
		if(tokens.contains(tokenName)){ //is it a terminal?
			temp.add(tokenName);
		}
		else{
			Fset aFirstSet = first.get(findInFirst(tokenName));
			temp = aFirstSet.getSet();
		}
		return temp;
	}
	
	public String theFirstSets(){
		String s = "";
		for(Fset set : first){
			s += set.toString() + "\n";
		}
		return s;
	}
	
	public String theFollowSets(){
		String s = "";
		for(Fset set : follow){
			s += set.toString() + "\n";
		}
		return s;
	}
	
	public String toString(){
		String s = "";
		for(LL1Node rule : grammar){
			s += rule.printRule() + "\n";
		}
		return s;
	}
	
	public String theNonTerminals(){
		String s = "";
		for(String ruleName : nonTerm){
			s += ruleName + " ";
		}
		return s;
	}
	
	public String printParseTable(){
		return parseTable.toString();
	}
	
	public boolean errorOcurred(){
		return errFound;
	}

	public String getErrLog() {
		return errLog;
	}

	public void setErrLog(String errLog) {
		this.errLog = errLog;
	}
}
